import java.util.List;
import java.util.LinkedList;
import java.util.Arrays;
import java.util.ArrayList;

/** Uma classe que implementa um tabuleiro do jogo Hex.
 * @author ei08150
 */

/* Forma como o tabuleiro e representado.
 * 
 * Consideremos um tabuleiro hexagonal 3 por 3, representado pelo
 * seguinte desenho:
 * 
 *       /-\ /-\ /-\
 *      |   |   |   |
 *      |   |   |   |
 *       \_/ \_/ \_/-\
 *        |   |   |   |
 *        |   |   |   |
 *         \_/ \_/ \_/-\
 *          |   |   |   |
 *          |   |   |   |
 *           \_/ \_/ \_/
 * 
 * Onde as linhas serao definidas com numeros e as colunas com letras,
 * como se ve no seguinte desenho:
 * 
 *        \   /-\ /-\ /-\
 *  1 -----X |   |   |   |
 *        /  |   |   |   |
 *            \_/ \_/ \_/-\
 *        \    |   |   |   |
 *  2 -----X   |   |   |   |
 *        /     \_/ \_/ \_/-\
 *           \   |   |   |   |
 *  3 --------X  |   |   |   |
 *           /    \_/ \_/ \_/
 * 
 *                  +-  +-   +-
 *                  |\  |\   |\
 *                    \   \    \
 *                     \   \    \
 * 
 *                       A   B    C
 * 
 * A primeira forma de representar o tabuleiro seria com um array de
 * array de inteiros, que seria criado de forma a representar o
 * formato hexagonal do ficheiro, recorrendo a ajuda de casas nao
 * validas.
 * 
 * Iria ficar algo semelhante a isto, onde o 1 representa uma casa
 * vazia e o 0 representa uma casa "nao-valida", isto e, so existe
 * para manter o formato do desenho:
 * 
 *  1 --->  [[1, 0, 1, 0, 1, 0, 0],
 *  2 --->   [0, 1, 0, 1, 0, 1, 0],
 *  3 --->   [0, 0, 1, 0, 1, 0, 1]]
 *                   +-    +-    +-
 *                   |\    |\    |\
 *                     A     B     C
 * 
 * Se se remover os zeros, ficaria algo assim:
 * 
 *  1 --->  [[1 1 1  ],    sem os []    1 ---> 1 1 1    
 *  2 --->   [ 1 1 1 ],   ----------->  2 --->  1 1 1   
 *  3 --->   [  1 1 1]]                 3 --->   1 1 1  
 *               + + +                            + + +   
 *                \ \ \                            \ \ \  
 *                 \ \ \                            \ \ \ 
 *                  A B C                            A B C
 * 
 * No entanto, ao observar este formato, pode-se ver que nao e
 * necessario o uso das casas "nao validas", isto e, o tabuleiro pode
 * ser representado da seguinte forma:
 * 
 *  1 --->  [[1, 1, 1],
 *  2 --->   [1, 1, 1],
 *  3 --->   [1, 1, 1]]
 *            +  +  +
 *            |  |  |
 *            A  B  C
 * 
 * Desde que a verificacao de caminhos seja feita da seguinte forma
 * (onde 3, representa a casa onde uma peca foi colocada e os 2
 * representam as casas que lhe estao ligadas):
 * 
 * 321   232   123   221   122   112   111   111   111
 * 211   221   112   321   232   123   221   122   112
 * 111   111   111   211   221   122   321   232   123
 * 
 *                          X
 *                         /|\
 *                           \
 *                            \_ O caso geral
 *
 */
public class Board {

	public static final int MIN_SIZE = 3;
	public static final int MAX_SIZE = 15;
	public static final int DEFAULT_SIZE = 7;

	/** Cria um tabuleiro do jogo Hex vazio.
	 * @param size Número de linhas e colunas do tabuleiro (>2).
	 */
	public Board(int size) {
		if(size < MIN_SIZE) size = MIN_SIZE;
		else if(size > MAX_SIZE) size = MAX_SIZE;

		board = new int[size][];
		for(int i = 0; i < size; i++)
			board[i] = new int[size];
	}

	public int getSize() {
		return board.length;
	}

	@Override
	public String toString() {
		String res = "  ";
		// Desenhar as letras no topo
		for(int i = 0; i < board.length; i++) {
			res += posNumberToLetter(i) + " ";
		}
		res += "\n";

		for(int i = 0; i < board.length; i++) {
			for(int s = 0; s < i; s++)
				res += ' ';
			
			res += posNumberToLetter(i) + "  ";

			for(int j = 0; j < board.length; j++) {
				switch(board[i][j]) {
					case Color.EMPTY: res += '_'; break;
					case Color.WHITE: res += 'O'; break;
					case Color.BLACK: res += 'X'; break;
				}
				res += ' ';
			}
			
			res += '\n';
		}

		return res;
	}

	/** Desenha o tabuleiro no ecrã.
	 */
	public void drawBoard() {
		System.out.println(toString());
	}

	public boolean isValidMove(Move move) {
		if(move.getLine() < 0 || move.getLine() >= getSize() ||
				move.getColumn() < 0 || move.getColumn() >= getSize())
			return false;

		int[] boardLine = board[move.getLine()];
		int valuePlace = boardLine[move.getColumn()];

		return (valuePlace == Color.EMPTY);
	}

	public void placePiece(int colorPiece, Move move) {
		// Antes de chamar esta função, deve ser verificada se a jogada é válida
		// com a função isValidMove()
		int[] boardLine = board[move.getLine()];

		boardLine[move.getColumn()] = colorPiece;
	}

	public boolean isPositionEmpty(int line, int column) {
		return board[line][column] == Color.EMPTY;
	}

	public boolean isPositionEmpty(Move move) {
		return board[move.getLine()][move.getColumn()] == Color.EMPTY;
	}

	public boolean isGameOver() {
		if (hasWhiteWon())
			return true;
		else if (hasBlackWon())
			return true;
		else
			return false;
	}

	public int getWinner() {
		if(!isGameOver())
			return Color.EMPTY;
		else {
			// FIXME: hasWhiteWon e hasBlackWon sao usados em
			// isGameOver. Para evitar ter que se calcular os caminhos
			// varias vezes, talvez seja melhor que isGameOver devolva
			// a Color do vencedor
			// XXX: Alguns testes feitos na interface gráfica parece
			// indicar que o algoritmo é rápido o suficiente, mesmo
			// para o tabuleiro de tamanho maximo

			if (hasWhiteWon())
				return Color.WHITE;
			else
				return Color.BLACK;
		}
	}

	public static char posNumberToLetter(int number) {
		return (char)('A' + number);
	}

	public static int posLetterToNumber(char letter) {
		return (int)(letter - 'A');
	}

	public int[][] getBoard() {
		return board;
	}

	// FIXME: Usar aqui b.board[i][j] implica que int[][] board seja
	// declarado como public. Nao deveria de ser um private?
	protected Board clone() {
		int size = getSize();
		Board b = new Board(size);
		for(int i = 0; i < size; i++)
			for(int j = 0; j < size; j++)
				b.board[i][j] = board[i][j];
		return b;
	}

	int[] convertListToArray(List<Integer> list) {
		int[] returnValue = new int[list.size()];

		for (int k = 0; k != list.size(); k++) {
			returnValue[0] = list.get(k);
		}

		return returnValue;
	}

	public List<int[]> adjacentPositions(int y, int x) {
		List<int[]> returnValue = new LinkedList<int[]>();

		// Se canto_sup_esquerdo
		//   [y][x+1] e [y+1][x]
		if (y == 0 && x == 0) {
			returnValue.add(convertListToArray(Arrays.asList(0, 1)));
			returnValue.add(convertListToArray(Arrays.asList(1, 0)));
		}
		// Se canto_sup_direito
		//   [y][x-1] e [y+1][x]
		else if (y == 0 && x == board[0].length-1) {
			returnValue.add(convertListToArray(Arrays.asList(0, x-1)));
			returnValue.add(convertListToArray(Arrays.asList(1, x)));
		}
		// Se canto_inf_esquerdo
		//   [y-1][x] e [y-1][x+1] e [y-1][x]
		else if (y == board.length-1 && x == 0) {
			returnValue.add(convertListToArray(Arrays.asList(y-1, 0)));
			returnValue.add(convertListToArray(Arrays.asList(y-1, 1)));
			returnValue.add(convertListToArray(Arrays.asList(y-1, 0)));
		}
		// Se canto_inf_direiro
		//   [y-1][x] e [y][x-1]
		else if (y == board.length-1 && x == board[0].length-1) {
			returnValue.add(convertListToArray(Arrays.asList(y-1, x)));
			returnValue.add(convertListToArray(Arrays.asList(y, x-1)));
		}
		// Se y == 0 (linha do topo)
		//   [y][x-1] e [y][x+1] e [y+1][x-1] e [y-1][x]
		else if (y == 0) {
			returnValue.add(convertListToArray(Arrays.asList(0, x-1)));
			returnValue.add(convertListToArray(Arrays.asList(0, x+1)));
			returnValue.add(convertListToArray(Arrays.asList(1, x-1)));
			returnValue.add(convertListToArray(Arrays.asList(1, x)));
		}
		// Se x == 0 (linha da esquerda)
		//   [y-1][x] e [y-1][x+1] e [y][x+1] e [y+1][x]
		else if (x == 0) {
			returnValue.add(convertListToArray(Arrays.asList(y-1, 0)));
			returnValue.add(convertListToArray(Arrays.asList(y-1, 1)));
			returnValue.add(convertListToArray(Arrays.asList(y, 1)));
			returnValue.add(convertListToArray(Arrays.asList(y+1, 1)));
		}
		// Se x == size (linha da direira)
		//   [y-1][x] e [y][x-1] e [y+1][x-1] e [y+1][x]
		else if (x == board[0].length-1) {
			returnValue.add(convertListToArray(Arrays.asList(y-1, x)));
			returnValue.add(convertListToArray(Arrays.asList(y, x-1)));
			returnValue.add(convertListToArray(Arrays.asList(y+1, x-1)));
			returnValue.add(convertListToArray(Arrays.asList(y+1, x)));
		}
		// Se y == size (linha do fundo)
		//   [y][x-1] e [y][x+1] e [y-1][x] e [y-1][x+1]
		else if (y == board.length-1) {
			returnValue.add(convertListToArray(Arrays.asList(y, x-1)));
			returnValue.add(convertListToArray(Arrays.asList(y, x+1)));
			returnValue.add(convertListToArray(Arrays.asList(y-1, x)));
			returnValue.add(convertListToArray(Arrays.asList(y-1, x+1)));
		}
		// Caso geral
		//   [y-1][x] e [y-1][x+1] e [y][x-1] e [y][x+1] e [y+1][x]
		else {
			returnValue.add(convertListToArray(Arrays.asList(y-1, x)));
			returnValue.add(convertListToArray(Arrays.asList(y-1, x+1)));
			returnValue.add(convertListToArray(Arrays.asList(y, x-1)));
			returnValue.add(convertListToArray(Arrays.asList(y, x+1)));
			returnValue.add(convertListToArray(Arrays.asList(y+1, x)));
		}
		
		return returnValue;
	}

	private int[][] transposeBoard() {
		int[][] transposed = new int[board[0].length][board.length];
		
		for(int rows = 0; rows < board.length; rows++){
			for(int cols = 0; cols < board[0].length; cols++){
				transposed[cols][rows] = board[rows][cols];
			}
		}

		return transposed;
	}

	public boolean hasWhiteWon() {
		return checkLineThroughBoard(transposeBoard(), Color.WHITE);
	}

	public boolean hasBlackWon() {
		return checkLineThroughBoard(board, Color.BLACK);
	}

	private boolean checkLineThroughBoard(int[][] boardToCheck, int color) {
		/* Verificar se existe pelo menos uma peca da cor indicada em
		 * cada linha do tabuleiro, caso nao exista e impossivel haver
		 * um caminho que va do topo ao fundo do tabuleiro
		 */
		for (int[] boardLine : boardToCheck) {
			boolean existsColoredPiece = false;

			for (int boardPlace : boardLine) {
				if (boardPlace == color) {
					existsColoredPiece = true;
				}
			}

			if (!existsColoredPiece) {
				return false;
			}
		}

		// Os caminhos so podem comecar do topo do tabuleiro
		for (int x = 0; x != boardToCheck[0].length; x++) {
			if (boardToCheck[0][x] == color) {
				if (checkLineThroughBoard(boardToCheck, 0, x, color)) {
					return true;
				}
			}
		}

		return false;
	}

	private boolean checkLineThroughBoard(int[][] boardToCheck, int y, int x, int color) {
		// Guarda uma lista de posicoes do tabuleiro pelas quais o
		// algoritmo ja atravessou
		List<int[]> passedPositions = new LinkedList<int[]>();

		return checkLineThroughBoard(boardToCheck, y, x, color, passedPositions);
	}

	private boolean checkLineThroughBoard(int[][] boardToCheck, int y, int x, int color, List<int[]> passedPositions) {
		
		// Final do passo recursivo: Chegar ao fundo do tabuleiro
		if (y == boardToCheck.length-1)
			return true;

		/* Posicoes verificadas (onde 3 corresponde ao ponto do
		 * tabuleiro indicado pelos argumentos y e x desta funcao e 2
		 * corresponde as posicoes do tabuleiro onde sera tentado
		 * continuar o caminho):
		 * 111
		 * 232
		 * 221
		 */

		/* Verificar esta situacao:
		 * 111
		 * 131
		 * 121
		 */
		if (boardToCheck[y+1][x] == color) {
			int[] boardPlace = {y+1, x};

			if (!listContainsBoardPlace(passedPositions, boardPlace)) {
				passedPositions.add(boardPlace);

				if (checkLineThroughBoard(boardToCheck, boardPlace[0], boardPlace[1], color, passedPositions)) {
					return true;
				}
			}
		}
		/* Verificar esta situacao:
		 * 111
		 * 132
		 * 111
		 */
		if (x != boardToCheck[0].length-1 && boardToCheck[y][x+1] == color) {
			int[] boardPlace = {y, x+1};

			if (!listContainsBoardPlace(passedPositions, boardPlace)) {
				passedPositions.add(boardPlace);

				if (checkLineThroughBoard(boardToCheck, boardPlace[0], boardPlace[1], color, passedPositions)) {
					return true;
				}
			}
		}
		
		/* Verificar esta situacao:
		 * 111
		 * 131
		 * 211
		 */
		if (x != 0 && boardToCheck[y+1][x-1] == color) {
			int[] boardPlace = {y+1, x-1};

			if (!listContainsBoardPlace(passedPositions, boardPlace)) {
				passedPositions.add(boardPlace);
			
				if (checkLineThroughBoard(boardToCheck, boardPlace[0], boardPlace[1], color, passedPositions)) {
					return true;
				}
			}
		}

		/* Verificar esta situacao:
		 * 111
		 * 231
		 * 111
		 */
		if (x != 0 && boardToCheck[y][x-1] == color) {
			int[] boardPlace = {y, x-1};

			if (!listContainsBoardPlace(passedPositions, boardPlace)) {
				passedPositions.add(boardPlace);

				if (checkLineThroughBoard(boardToCheck, boardPlace[0], boardPlace[1], color, passedPositions)) {
					return true;
				}
			}
		}

		return false;
	}

	private boolean listContainsBoardPlace(List<int[]> list, int[] boardPlace) {
		for (int[] place : list) {
			if (place[0] == boardPlace[0]
				&& place[1] == boardPlace[1]) {
				return true;
			}
		}

		return false;
	}

	int[][] board;
}

class NonEmptySquare extends Exception {}
